package string;

/**
 *
 */
public class RegularExpressionMatch {

    public static void main(String[] args) {
        System.out.println(isMatch("abc", ".bc"));
        System.out.println(isMatch("abc", "bc"));
        System.out.println(isMatch("abc", ".*bc"));
        System.out.println(isMatch("abc", "a*bc"));
        System.out.println(isMatch("aaaaaaaaaaabc", "a*bc"));
    }

    public static boolean isValid(char[] s, char[] e) {

        // 原始串不能有点和*
        for (char c : s) {
            if (c == '*' || c == '.') {
                return false;
            }
        }

        // *号不能为第一个 且两个*不能相连
        for (int i = 0; i < e.length; i++) {
            if (e[i] == '*' && (i == 0 || e[i - 1] == '*')) {
                return false;
            }
        }

        return true;
    }

    public static boolean isMatch(String str, String exp) {
        if (str == null || exp == null) {
            return false;
        }

        char[] s = str.toCharArray();
        char[] e = exp.toCharArray();

        return isValid(s, e) && process(s, e, 0, 0);
    }

    /**
     * s[si..]能否被e[ei..]匹配出来
     * 必须保证ei压中的不是*
     *
     * @param s  原始串
     * @param e  匹配串
     * @param si 原始串对应匹配的下标
     * @param ei 匹配串对应匹配的下标
     * @return true 可以匹配，不能匹配
     */
    private static boolean process(char[] s, char[] e, int si, int ei) {
        // base case exp已经耗尽
        if (ei == e.length) {
            // 表达式串没有的时候，原始串也没有了，就表示匹配成功
            return si == s.length;
        }

        // 可能性1，ei位置后面没有字符了  ||  ei + 1位置，不是*
        if (ei + 1 == e.length || e[ei + 1] != '*') {
            // 原始串不为空 &&（str[si]必须和exp[ei]相等 || exp[ei]位置是通配符[.]）&& 并且剩余的后面部分能走通
            return si != s.length && (e[ei] == s[si] || e[ei] == '.') && process(s, e, si + 1, ei + 1);
        }

        // ei + 1位置是*
        // 原始串没结束 && （当前值对应相等 || 表达式是 [.*] 这样子，）
        while (si != s.length && (e[ei] == s[si] || e[ei] == '.')) {
            if (process(s, e, si, ei + 2)) {
                return true;
            }
            si++;
        }

        // 原始串结束了 || （当前值不相等 || 表达式不是 [.*] 这样子，）
        // 则把表达式 [x*]的部分当前0个x字符处理，跳到表达式下下个字符，接着比配
        return process(s, e, si, ei + 2);
    }


    public static boolean isMatchDP(String str, String exp) {
        if (str != null || exp == null) {
            return false;
        }

        char[] chars = str.toCharArray();
        char[] e = exp.toCharArray();

        if (!isValid(chars, e)) {
            return false;
        }


        boolean[][] dp = initDPMap(chars, e);


        for (int i = chars.length - 1; i >= 0; i--) {
            for (int j = e.length - 2; j >= 0; j--) {
                if (e[j + 1] != '*') {
                    // 当前位置可以匹配，后面的部分也能匹配
                    dp[i][j] = (chars[i] == e[j] || e[j] == '.') && dp[i + 1][j + 1];
                } else {
                    // ei + 1位置是*
                    // 原始串没结束 && （当前值对应相等 || 表达式是 [.*] 这样子，）
                    int si = i;
                    while (si != chars.length && (chars[si] == e[j] || e[j] == '.')) {
                        if (dp[si][j + 2]) {
                            dp[i][j] = true;
                            break;
                        }
                        si++;
                    }

                    // 原始串结束了 || （当前值不相等 || 表达式不是 [.*] 这样子，）
                    // 则把表达式 [x*]的部分当前0个x字符处理，跳到表达式下下个字符，接着比配
                    if (!dp[i][j]) {
                        dp[i][j] = dp[si][j + 2];
                    }
                }
            }
        }

        return dp[0][0];
    }

    private static boolean[][] initDPMap(char[] chars, char[] e) {
        int slen = chars.length;
        int elen = e.length;

        boolean[][] dp = new boolean[slen + 1][elen + 1];


        // 表达式串没有的时候，原始串也没有了，就表示匹配成功
        // 最右下角为true，最后一列的其他位置都为false，表示原始串还有，但是表达式没有了
        dp[slen][elen] = true;

        // 填dp表最后一列的值，剩下的表达式能不能匹配出空串
        for (int j = elen - 2; j >= 0; j = j - 2) {
            if (e[j] != '*' && e[j + 1] == '*') {
                // 可以使用[x*]代表空串比配出最后的空串
                dp[slen][j] = true;
            } else {
                // 有一次不满足，则左边剩下的格子都为默认的false
                break;
            }
        }


        if (slen > 0 && elen > 0) {
            // 当前表达式和原始串只有一个字符时
            // 字符相等 || 表达式最后一个字符是逗号才能匹配成功
            if ((e[elen - 1] == '.' || chars[slen - 1] == e[elen - 1])) {
                dp[slen - 1][elen - 1] = true;
            }
        }

        return dp;
    }
}
